package array

import "math"

func numSquares(n int) int {

	amount := int(math.Sqrt(float64(n)))

	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dp[i] = math.MaxInt32 - 1
	}
	dp[0] = 0

	for i := 1; i <= n; i++ {
		for j := 1; j <= amount; j++ {
			if i-(j*j) >= 0 {
				if dp[i-(j*j)]+1 < dp[i] {
					dp[i] = dp[i-(j*j)] + 1
				}
			}
		}
	}
	return dp[n]
}
